#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include "AvlTree.h"
#include <sys/time.h>

using namespace std;

int main()
{
  int num[] = {100, 1000, 10000, 100000, 1000000};
  double timeusingN[sizeof(num)/sizeof(num[0])]; //单位为ms
  AvlTree<int> avlt;
  vector<int> array;
  
  //展示算法可行性
  for(int i=0; i<num[0]; i++)
  	avlt.insert(i+1);
  avlt.printTreeinrange(10, 20);
  avlt.readTreeinrange(10, 20, array);
  for(int i=0; i<=10; i++)
  	cout << array[i] << " ";
  cout << endl;
  avlt.makeEmpty();
  array.clear();
  
  //数值验证复杂度
  //固定K=100，查看规模N对时间复杂度的影响，结果保存在timeusingN
  struct timeval time;
  double start,stop;
  for(int j=0; j<(sizeof(num)/sizeof(num[0])); j++)
  {
	  for(int i=0; i<num[j]; i++)
			avlt.insert(i+1);
		gettimeofday(&time, nullptr);
		start = time.tv_usec;
		
		avlt.readTreeinrange(1, 100, array);
		gettimeofday(&time, nullptr);
		stop = time.tv_usec;
		
		cout << "K=100, \t"<<"N=" << num[j] << "   \t" << "time=" << double(stop-start) << "ms" <<endl;
		array.clear();
		avlt.makeEmpty();
	}
  
  //固定N=1000000， 查看K对时间复杂度的影响，结果直接打印出来
  for(int i=0; i<num[4]; i++)
  	avlt.insert(i+1);
  for(int j=0; j<(sizeof(num)/sizeof(num[0])); j++)
  {
  	gettimeofday(&time, nullptr);
  	start = time.tv_usec;
  	avlt.readTreeinrange(1, num[j], array);
  	gettimeofday(&time, nullptr);
		stop = time.tv_usec;
  	cout << "N=1000000, " << "K=" << num[j] << "\t" << "time=" << double(stop-start) << "ms" << endl;
  	array.clear();
  }
  
  return 0;
}
